高级算法之Markov Chain Monte Carlo methods

Posted on

Markov Chain Monte Carlo(MCMC) methods

问题: 样本空间$U$, 子集$S\subset U$, $\rho=|S|/|U|$, 假设有一个从$U$中的均匀随机采样器, 估计$Z=|S|$.

蒙特卡洛法:

从$U$中独立均匀随机采样$X_1, X_2,\cdots,X_N$,

则

Estimator Theorem:

$N\ge \frac{4}{\epsilon^2\rho}\ln \frac{2}{\delta}$, 则$\Pr[\hat Z\text{ is }\epsilon\text{-approx of }|S|]\ge 1-\delta$, 即$\Pr[(1-\epsilon)Z\le \hat Z\le (1+\epsilon)Z]\ge 1-\delta$.
证明直接使用Chernoff Bound:
令$Y=\sum_{i=1}^NY_i$, $\mathbb E[Y]=\rho N$,

另一个方向同理(概率小于等于$e^{-\epsilon^2\rho n/2}$).

Counting DNF Solutions

输入: DNF公式$\phi: \{T,F\}^n\to\{T,F\}$
输出: 满足解的个数$Z=|\phi^{-1}(T)|$

  • n个布尔变量: $x_1, x_2,\cdots,x_n\in\{\text{true, false}\}$
  • DNF: $\phi=C_1\lor C_2\lor \cdots\lor C_m$
  • m个子句$C_1,\cdots,C_m$
  • 每个子句为$C_i=l_{i_1}\land l_{i_2}\land\cdots\land l_{i_k}$
  • 每个文字: $l_j\in\{x_r,\neg x_r\}$对于某个$r$
    数DNF是$# P$难的(比NP难还难)
  • $U=\{T,F\}^n$, $S=\{x\in\{T,F\}^n|\phi(x)\}=\phi^{-1}(T)$
  • $\rho$可能是指数小的. 例如当DNF是一个很大的子句时

Union of sets

输入: $m$个集合$S_1,S_2,\cdots, S_m$, 估计集合$S=\cup_{i=1}^m S_i$的大小
定义:

  • $U=S_1\biguplus S_2 \biguplus \cdots\biguplus S_m=\{(x,i)|x\in S_{i}\}$,
  • $U=\{(x,i^{*})|x\in S_{i^{*}}\text{ and }x\in S_i=>i^{*}\le i\}$
    ($i^{*}$是最小的那个),
    则$|\overline S|=|S|$, $\overline S\subseteq U$, $\rho = \frac{|\overline S|}{|U|}\ge \frac{1}{m}$

蒙特卡洛方法:

  • 均匀采样$(x,i)\in U$ ($N=\Theta(\frac{m}{\epsilon^2}\ln \frac{1}{\delta})$次独立的). 对于每个采样, 判断是否有$(x,i)\in\overline S$.
    并且要统计每个$S_i$的大小, 加起来得到$|U|$, 然而使用Estimator Theorem即可.
    $\rho=\frac{|\overline S|}{|U|}\ge 1/m$是因为$\overline S$中每个元素至多在$U$中出现m次

CSP均匀采样的两种方法

输入一个CSP实例, 采样一个均匀随机的CSP解.

Metropolis Algorithm:

初始: 一个任意的CSP解;
每一步当前CSP解为$\sigma=(\sigma_1,\cdots,\sigma_n)$

  • 提议: 均匀随机选择变量$i\in[n]$, $c\in[q]$;
  • 滤波: 如果改变后依然满足所有限制, 把$\sigma_i$改为$c$.
    在T步之后返回$\sigma$.
  • MCMC: 第一个MC对应随机游走, 第二个MC表示停下了的时候不是完美的, 有一定的偏置

Glauber Dynamics(Gibbs sampling)

从任意解出发

  • 随机选择$i\in[n]$
  • 根据$\sigma_i$以外的变量的当前取值, 算出$\sigma_i$的所有可行取值, 在这些可行取值中均匀随机采样, $\sigma_i$改为采样到的值.
    (根据第i个变量的条件为其他变量当前取值的边缘分布)
    在T步之后返回$\sigma$.
    这两个算法最终都收敛到均匀分布.
    收敛速率分析是很难的.

随机游走

随机过程

$\{X_t|t\in T\}$, $X_t\in \Omega$.
离散时间$T=\{0,1,\cdots\}$
离散空间$\Omega$是有穷的或者可数无穷的
$X_0,X_1,\cdots$
马尔科夫链:
$\forall t=0,1,\cdots,\forall x_0,x_1\cdots,x_{t-1},x,y\in\Omega$
$\Pr[X_{t+1}=y|X_0=x_0,\cdots,X_{t-1}=x_{t-1},X_t=x]=\Pr[X_{t+1}=y|X_t=x]=P_{xy}^{(t)}$
即和之前哪来的无关, 只和当前位置有关(无记忆的)
homogeneity: 转移规则和时间无关, 即$P_{xy}^{(t)}=P_{xy}$. 下面只考虑这种.
转移矩阵P: $\Omega\times\Omega$ 的转移矩阵$P$, 每一行加起来是1
已知$X_t$的分布, 根据全概率公式, 就可以得到$X_{t+1}$的分布, 即$P^{(t+1)}=p^{(t)}P$
稳态分布$\pi$: $\pi P=\pi$(不动点)

马尔科夫链基本定理:

如果一个有穷马尔科夫链$M=(\Omega,P)$是不可约且无周期的, 那么任意初始分布$\pi^{(0)}$,

其中$\pi$是唯一的稳态分布, 满足$\pi P=\pi$
坏情况

  • 实际不连通, 有无穷多个稳态分布
  • 有周期
    不可约: 所有的状态对都是互通(强连通)的. 否则$P=\left[\begin{matrix}P_A & 0\\0&P_B\end{matrix}\right]$
    无周期性: 定义$d_x=\gcd\{t|P^t(x,x)>0\}$, 即有长为t的x到x的环. 无周期性即每个状态的周期都是1.
    1一定是右特征值, 而左特征值和右特征值是一一对应的, 所以1也是左特征值, 而左特征向量非负(Perron-Frobenius Theorem非负矩阵的最大特征值对应的特征向量一定是非负的), 所以稳态分布一定存在

图上的随机游走

无向图$G(V,E)$中:

均匀随机游走:

  • 每一步均匀随机选取一个邻居走过去

  • 转移矩阵

  • 不可约: $G$是连接的

  • 无周期: $P(x,y)>0$
    懒惰随机游走:
  • 一半概率什么都不做,
  • 一半概率随机选取一个邻居走过去
  • 转移矩阵
  • 这两种的稳态分布都是:
  • 对于均匀随机游走,
  • 对于懒惰游走, $P’=\frac{1}{2}(I+P)$, $\pi P=\pi$, 所以$\pi P’=\pi$

Reversibility

Detailed Balance Equation(DBE):

时间可逆time-reversible Markov chain:

时间可逆time-reversible Markov chain一定是stationary distribution:

时间可逆: 从$\pi$开始

在图上的游走中

  • 在$u=v$或者$u\not\sim v$时, DBE成立;
  • 在$u\sim v$时, DBE成立当

如果想要得到稳态是均匀分布, 则转移矩阵为

其中$\Delta=\max_vdeg(v)$.

Metropolis Algorithm

  • 状态空间$\Omega$上的对称的转移矩阵$Q$:
    $Q^T=Q$, $Q1=1$ ==> $1Q=1$ 稳态分布
  • 每一步中, 当前状态是$x\in \Omega$
    • 提议: 以概率$Q(x,y)$提议$y\in \Omega$
    • 滤波: 接受提议, 以概率$\min\{1,\pi(y)/\pi(x)\}$移动到$y$
  • 对于$x\ne y$, $P(x,y)=Q(x,y)\min\{1,\frac{\pi(x)}{\pi(y)}\}$
  • 对于$x=y$, $P(x,x)=1-\sum_{y\ne x}P(x,y)$.
  • 满足DBE, 是均匀稳态分布

Glauber Dynamics

每一步中, 当前状态是$X=(X_1,\cdots,X_n)$:

  • 均匀随机选择$i\in [n]$
  • 根据$X_i$的当前边界分布(除了$X_i$以外的都固定为当前值), 采样$X_i$
    也满足DBE, 是均匀稳态分布

Mixing Time

到达稳态的时间. 具体见讲义.